package floyd;

import java.util.ArrayList;
import java.util.List;

import distance.LatLng;

public class Floyd {
	private static int INF = Integer.MAX_VALUE;
	private int[][] dist;
	private int[][] path;
	private List result = new ArrayList();
	
	
	public int[][] getDist() {
		return dist;
	}
	public int[][] getPath() {
		return path;
	}
	public List getResult() {
		return result;
	}

	public void findCheapestPath(int begin, int end, int[][] matrix) {
		Floyd(matrix);
		result.add(begin);
		findPath(begin, end);
		result.add(end);
	}

	public void findPath(int i, int j) {
		int k = path[i][j];
		if (k == -1)
		return;
		findPath(i, k);
		result.add(k);
		findPath(k, j);
	}

	public void Floyd(int[][] matrix) {
		int size = matrix.length;
		for (int i = 0; i < size; i++) {
			for (int j = 0; j < size; j++) {
				path[i][j] = -1;
				dist[i][j] = matrix[i][j];
			}
		}
		for (int k = 0; k < size; k++) {
			for (int i = 0; i < size; i++) {
				for (int j = 0; j < size; j++) {
					if (dist[i][k] != INF && dist[k][j] != INF&& dist[i][k] + dist[k][j] < dist[i][j]) {
						dist[i][j] = dist[i][k] + dist[k][j];
						path[i][j] = k;
					}
				}
			}
		}
		
 		Dyadic.draw(size, dist);
	}
	
	public Floyd(int size){
		this.path = new int[size][size];
		this.dist = new int[size][size];
	}
	
	/*public static void main(String arg[]) {
		Floyd graph = new Floyd(5);
		int[][] matrix ={
							{ 0, 3, 8, INF, 4 }, 
							{ INF, 0, INF, 1, 7 },
							{ INF, 4, 0, INF, INF }, 
							{ 2, INF, 5, 0, INF },
							{ INF, INF, INF, 6, 0 }
						};
		int begin = 4;
		int end = 1;
		graph.findCheapestPath(begin,end,matrix);
		List list = graph.result;
		System.out.println("The shortest path " + begin + " -> " + end + " is: ");
		
		System.out.println(list.toString());
		
		System.out.println("The length of shortest path is " + graph.dist[begin][end]);
	}*/
	
}
